#include <vector>
#include <stack>
#include <utility>
#include <stdexcept>
#include <algorithm>
#include <cmath>
#include "Generators.h"

#include "StronglyConnectedComponentsGraph.h"
#include "testTarjan.h"

void trivialTarjanCheck(const Graph &G, const std::vector<int>& componentsList){
	std::vector<colors> vertexColors(G.getVertexNum(), WHITE);
	std::stack<int> vertexStack;
	std::vector<std::vector<int> > adjacentList(G.getVertexNum());

	std::vector<int> parentsList(G.getVertexNum());
	std::vector<std::vector<bool> > linkBetweenVertexes(G.getVertexNum(), std::vector<bool>(G.getVertexNum(), false));

	SimpleDfsClass currentUserClass;
	for (int currentVertex = 0; currentVertex < G.getVertexNum(); ++currentVertex){
		vertexColors.assign(G.getVertexNum(), WHITE);
		vertexStack.push(currentVertex);
		currentUserClass.clearData();
		DFSStep(G, &currentUserClass, &vertexStack, &vertexColors, &adjacentList, &parentsList, currentVertex);
		std::vector<int> reachebleList = currentUserClass.getDFSOrder();
		for (auto toVertex : reachebleList){
			linkBetweenVertexes[currentVertex][toVertex] = true;
		}
	}

	for (int firstVertex = 0; firstVertex < G.getVertexNum(); ++firstVertex){
		for (int secondVertex = 0; secondVertex < G.getVertexNum(); ++secondVertex){
			if (linkBetweenVertexes[firstVertex][secondVertex] && linkBetweenVertexes[secondVertex][firstVertex] &&
				(componentsList[firstVertex] != componentsList[secondVertex])){
				throw std::logic_error("Wrong finding strongly components");
			}
		}
	}
}


void stressRandomTarjanCheck(){
	for (int testNumber = 0; testNumber < 100; ++testNumber){
		std::cout << testNumber << std::endl;
		std::unique_ptr<Graph> G = generateGraph();
		StronglyComponentsFindClass tarjanClass(G->getVertexNum());
		DFS(*G, &tarjanClass);
		std::vector<int> componentsList = tarjanClass.getComponentsList();
		trivialTarjanCheck(*G, componentsList);
	}
}

std::vector<int> getMaskArray(int mask, int maskSize){
	std::vector<int> maskArray(maskSize);
	for (int currentPosition = 0; currentPosition < maskSize; ++currentPosition){
		maskArray.push_back(mask % 3);
		mask /= 3;
	}
	return maskArray;
}

void stressAllSmallGraphs(){
	for (int vertexNum = 1; vertexNum <= 6; ++vertexNum){
		int overallMasksCount = pow(3, vertexNum*(vertexNum - 1) / 2) + 0.01;
		for (int currentMask = 0; currentMask < overallMasksCount; ++currentMask){
			std::vector<Edge> edgesList;
			std::vector<int> maskArray = getMaskArray(currentMask, vertexNum*(vertexNum - 1) / 2);
			int positionInMask = 0;
			for (int firstVertex = 0; firstVertex < vertexNum; ++firstVertex){
				for (int secondVertex = firstVertex + 1; secondVertex < vertexNum; ++secondVertex){
					if (maskArray[positionInMask] == 1){
						edgesList.push_back({ firstVertex, secondVertex });
					}
					else if (maskArray[positionInMask] == 2){
						edgesList.push_back({ secondVertex, firstVertex });
					}
					positionInMask++;
				}
			}
			std::unique_ptr<Graph> G = readGraph(vertexNum, edgesList);
			StronglyComponentsFindClass componentClass(vertexNum);
			DFS(*G, &componentClass);
			std::vector<int> componentsList = componentClass.getComponentsList();
			trivialTarjanCheck(*G, componentsList);
		}
	}
}

void stressRandomShuffleTests(){
	for (int testNumber = 0; testNumber < 100; ++testNumber){
		std::cout << testNumber << std::endl;
		int vertexNum;
		std::vector<Edge>edgesList;
		generateScriptForGraph(vertexNum, edgesList);
		std::unique_ptr<Graph> G = readGraph(vertexNum, edgesList);
		std::vector<int> permutation(vertexNum);
		for (int position = 0; position < vertexNum; ++position){
			permutation[position] = position;
		}
		std::random_shuffle(permutation.begin(), permutation.end());
		for (size_t currentEdge = 0; currentEdge < (int)edgesList.size(); ++currentEdge){
			edgesList[currentEdge].fromVertex = permutation[edgesList[currentEdge].fromVertex];
			edgesList[currentEdge].toVertex = permutation[edgesList[currentEdge].toVertex];
		}
		std::random_shuffle(edgesList.begin(), edgesList.end());
		std::unique_ptr<Graph> permutationGraph = readGraph(vertexNum, edgesList);
		StronglyComponentsFindClass componentsForGraph(vertexNum), componentsForPermutationGraph(vertexNum);
		DFS(*G, &componentsForGraph);
		DFS(*permutationGraph, &componentsForPermutationGraph);
		std::vector<int> componentsList = componentsForGraph.getComponentsList();
		std::vector<int> componentsListPermutation = componentsForPermutationGraph.getComponentsList();
		for (int firstVertex = 0; firstVertex < vertexNum; ++firstVertex){
			for (int secondVertex = firstVertex + 1; secondVertex < vertexNum; ++secondVertex){
				if ((componentsList[firstVertex] == componentsList[secondVertex]) !=
					(componentsListPermutation[permutation[firstVertex]]
					== componentsListPermutation[permutation[secondVertex]])){
					throw std::logic_error("Components search depends on order of vertexes");
				}
			}
		}
	}
}

void stressCondensationTest(){
	for (int testNumber = 0; testNumber < 100; ++testNumber){
		std::cout << testNumber << std::endl;
		int vertexNum;
		std::vector<Edge> edgesList;
		generateScriptForGraph(vertexNum, edgesList);
		std::unique_ptr<Graph> G = readGraph(vertexNum, edgesList);
		StronglyComponentsFindClass componentsClass(vertexNum);
		DFS(*G, &componentsClass);
		std::vector<int> componentsList = componentsClass.getComponentsList();
		std::unique_ptr<Graph> condensatedGraph = buildingCondenstaionGraph(*G, componentsList);

		std::set<Edge> condensatedEdgesList;
		std::set<Edge> needEdgesList;
		int vertexCondensatedNum = condensatedGraph->getVertexNum();
		
		for (int currentVertex = 0; currentVertex < vertexCondensatedNum; ++currentVertex){
			std::vector<int> currentAdjacentList = condensatedGraph->getAdjacentList(currentVertex);
			for (auto currentToVertex : currentAdjacentList){
				condensatedEdgesList.insert(Edge(currentVertex, currentToVertex));
			}
		}
		for (int currentVertex = 0; currentVertex < vertexNum; ++currentVertex){
			std::vector<int> adjacentList = G->getAdjacentList(currentVertex);
			int fromVertexComponent = componentsList[currentVertex];
			for (auto currentToVertex : adjacentList){
				if (componentsList[currentToVertex] != fromVertexComponent){
					needEdgesList.insert(Edge(fromVertexComponent, componentsList[currentToVertex]));
				}
			}
		}

		for (const auto& currentEdge : needEdgesList){
			if (condensatedEdgesList.count(currentEdge) == 0){
				throw std::logic_error("Wrong condensation");
			}
		}
		for (const auto& currentEdge : condensatedEdgesList){
			if (needEdgesList.count(currentEdge) == 0){
				throw std::logic_error("Wrong condensation");
			}
		}
	}
}

